import java.util.HashMap;

public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        
        /*
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i : array) {
            int value = map.getOrDefault(i, 0) + 1;
            if (value > array.length / 2)
                return i;
            map.put(i, value);
        }

        return -1;
        */

        // 摩尔投票
        int x = -1;
        int cnt = 0;

        for (int i : array) {
            if (cnt == 0) {
                x = i;
                cnt++;
            }
            else {
                cnt += (x == i) ? 1 : -1;
            }
        }

        cnt = 0;
        for (int i : array) {
            cnt += (i == x) ? 1 : 0;
        }
        return (cnt > array.length/2) ? x : 0;

    }
}